package com.Leetcode;

import java.util.LinkedList;
import com.structure.ListNode;

public class AddTwoNumbers {

	public static void main(String[] args) {
		int[] a = {7,2,4,3};
		int[] b = {5,6,4};
		ListNode l1 = createList(a);
		ListNode l2 = createList(b);
		AddTwoNumbers addTwoNumber = new AddTwoNumbers();
		ListNode li = addTwoNumber.addTwoNumbers(l1, l2);
		if (li == null) {
            System.out.println("[]");
        }
    
        String result = "";
        while (li != null) {
            result += Integer.toString(li.val) + ", ";
            li = li.next;
        }
        System.out.println("[" + result.substring(0, result.length() - 2) + "]");
	}
	
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		ListNode p = null;
		LinkedList<Integer> list1 = new LinkedList();
		LinkedList<Integer> list2 = new LinkedList();
		int carry = 0,sum = 0;
		
        while(l1 != null) { list1.push(l1.val); l1 = l1.next; }
        while(l2 != null) { list2.push(l2.val); l2 = l2.next; }

        int len = Math.max(list1.size(),list2.size());
        while(len -- > 0 || carry != 0) {
        	int i = list1.isEmpty() ? 0:list1.pop();
        	int j = list2.isEmpty() ? 0:list2.pop();
        	sum = (i + j + carry);
        	carry = sum / 10;
        	sum %= 10;
        	ListNode node =  new ListNode(sum);
        	node.next = p;
        	p = node;
		}
		return p;
    }
	
	public static ListNode createList(int[] num) {
		ListNode p = new ListNode();
		ListNode header = p;
		for (int i = 0; i < num.length; i++) {
			p.next = new ListNode(num[i]);
			p = p.next;
		}
		return header.next;
	}
}

